package org.basis.algorithm.sort;

import org.basis.algorithm.sort.common.SortUtil;

/**
 * 快速排序
 *
 * @author Mr_wenpan@163.com 2022/02/11 09:56
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {1, 30, 22, 90, 20, 77, 33, 55, 66, 8, 5, 9, 3, 0, 10, 7, 2, 3, 9, 8, 2, 2, 5, 1, 2, 4, 5};
        quickSort(arr);
        SortUtil.printArr(arr);
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        doQuickSort(arr, 0, arr.length - 1);
    }

    public static void doQuickSort(int[] arr, int left, int right) {
        // base case
        if (left >= right) {
            return;
        }
        // 分区，分为左边是比某数小的，中间是等于某数的，右边是大于某数的
        int[] partition = partition(arr, left, right);
        // 对左右区间都进行同样的操作
        doQuickSort(arr, left, partition[0]);
        doQuickSort(arr, partition[1], right);
    }

    /**
     * 分区，将arr数组的左边分为比某个目标数小的数，右边是比某个目标数大的数，中间是等于某个目标数的数（荷兰国旗问题🇳🇱）
     */
    public static int[] partition(int[] arr, int left, int right) {
        // 左右指针及游标
        int l = left - 1;
        int r = right;
        int index = left;

        while (index < r) {
            // 当前数小于目标数，则放在左边界
            if (arr[index] < arr[right]) {
                // 交换后index处的数一定是等于目标数，所以index可以放心++
                SortUtil.swap(index++, ++l, arr);
                // 当前数大于目标数，则放在右边界
            } else if (arr[index] > arr[right]) {
                // 这里index不能++，因为换到index位置的数大小不定
                SortUtil.swap(index, --r, arr);
            } else {
                // 遇到等于目标数的数字，index直接向前走一步
                index++;
            }
        }

        // 交换最后一个数
        SortUtil.swap(right, index, arr);

        return new int[]{l, r + 1};
    }

}
